/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @author zhongfang
 *
 */
public class MinimumFactorization {
	static int[] factPos={2,3,5,7,9};
    public static int smallestFactorization(int a) {
    	int result=0;
        ArrayList<ArrayList<Integer>> factors=new ArrayList<>();
        int minLen=Integer.MAX_VALUE;
        for(int i=2;i<10;i++){
        	if(a%i==0){
        		int x=a/i;
        		ArrayList<Integer> tmp=new ArrayList<>();
        		tmp.add(i);
        		boolean tag=false;//是否可能
        		for (int integer : factPos) {
					if(x%integer==0){
						tag=true;
						break;
					}
				}
        		if(tag==false){
        			continue;
        		}
        		tag=true;
        		//所有可能的组成
        		while (x>9) {
					//找到x的因子
        			int tmpX=x;
        			for (int j = 2; j < 10; j++) {
						if(tmpX%j==0){
							tmp.add(j);
							tmpX/=j;
							break;
						}
					}
        			if(x==tmpX){//没有因子
        				tag=false;
        				break;
        			}
        			x=tmpX;
				}//end while
        		
        		tmp.add(x);
        		
        		if(tag==true){
        			factors.add(tmp);
        			minLen=Integer.min(minLen, tmp.size());
            		//用tmp拼成的result
        		}
        	}
        }
        System.out.println(factors);
        //在所有factor中选size最小的，依次拼出来
        for (ArrayList<Integer> arrayList : factors) {
        	if(arrayList.size()==minLen){
        		String string="";
        		Collections.sort(arrayList);
        		for (Integer integer : arrayList) {
        			string+=integer;
				}
        		try {
					result=Integer.parseInt(string);
					return result;
				} catch (Exception e) {
					
				}
        	}
		}
        return 0;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(smallestFactorization(256));
	}

}
